package leetcode.hot100;

public class Solution279 {

    public static void main(String[] args) {

       int count =  new Solution279().numSquares(12);
        System.out.println(count);
    }

    public int numSquares(int n) {
        int[] dp = new int[n+1];
        //先把平方数的位置置为1,平方数+1的位置置为2
        for (int i = 1; i*i <=n ; i++) {
            int squre = i*i;
            dp[squre] = 1;
            if(squre<n) dp[squre+1] = 2;
        }
        //一般的数就得遍历了
        for (int j = 1; j <=n; j++) {
            if(dp[j]==0){ //只处理还没确切值的地方
                //dp[n]=min{dp[n-i*i]+1}=min{dp[n-i*i]}+1, 1<=i<=sqrt(n)
                int tmp = 10000;
                for (int k = 1; k*k < j; k++) {
                    int squre = k*k;
                    tmp = Math.min(tmp,dp[j-squre]);
                }
                dp[j] = tmp+1;
            }
        }
        return dp[n];
    }

    public int numSquares1(int n) {
        //开方，开到没有余数为止，失败的贪心算法
        int count = 0, bigRoot = 0;
        while(n!=0){
            bigRoot = (int)Math.floor(Math.sqrt(n));
            n -= bigRoot*bigRoot;
            count++;
        }
        return count;
    }
}
